package Leetcode.图;

/**
 * @Author: kirito
 * @Date: 2024/9/8 16:38
 * @Description: 给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，
 * 当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
 *
 * 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，
 * 那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
 *
 * 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
 *
 * 如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
 *
 * 请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。
 *
 * 示例 1：
 *
 * 输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
 * 输出：0
 * 示例 2：
 *
 * 输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
 * 输出：0
 * 示例 3：
 *
 * 输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
 * 输出：1
 */

public class 尽量减少恶意软件的传播 {
    private boolean[] visited;    // 标记节点i是否访问过
    private int infects;            // 一个连通块上初始感染节点数
/*  https://leetcode.cn/problems/minimize-malware-spread/solutions/2743404/javapython3cdfsha-xi-biao-zhao-dao-zhi-b-9m5a/
    这道题要求是从初始感染节点中去除一个节点，使得最终感染节点数最少。我们来看，对于一个包含了初始感染节点的 连通块：

    只有一个初始感染节点，去除掉这个感染节点，这个连通块上就没有初始感染节点了，即整个连通块的不会被感染，减少的感染节点数为 m
    多于一个初始感染节点，无论去掉哪一个，剩下的感染节点依旧能将整个连通块的其他节点感染。

    因此我们的目标就是找到只有一个感染节点的最大连通块（只有一个初始感染节点的连通块的可以减少感染节点量为 m，
    为了使结果最小，就要让 m 最大）。如果有多个连通块尺寸一样，返回索引最小的那个节点。

    如果没有只有一个初始感染节点的连通块，那么无论去掉哪个连通块的哪个初始感染节点都一样，因此我们要找的就是初始感染节点的最小索引。

    因此我们去遍历一个连通块需要得到两个信息：

    这个连通块上的初始感染节点个数 infects；
    这个连通块的尺寸，即节点个数 cnts；
    我们可以利用深度优先搜索遍历每一个连通块：

    对于每个遍历到的节点判断是否为初始感染节点。为了快速判断，我们可以将初始感染节点列表转为哈希表；
    将遍历过节点标记为已标记 visited[node] = true；
    遍历 node 的所有邻节点，并累加节点个数 cnt；
    因为我们只关注包含感染节点的连通块，因此我们可以枚举初始感染节点列表的节点作为深度优先搜索的起始节点。
    如果节点已访问说明其所在连通块已处理。

    这哥们写的题解真的通透！！！
    */
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        boolean[] initial_set = new boolean[n];     // 将列表转为集合，用于快速判断一个节点是否为初始感染节点
        int min_index = initial[0];     // 初始感染节点的最小索引
        for(int init: initial){
            initial_set[init] = true;
            min_index = Math.min(min_index, init);
        }
        visited = new boolean[n];

        int maxSize = 0;    // 最大连通块尺寸
        int res = -1;       // 结果

        for(int root: initial){
            if(visited[root])continue;      // 跳过已访问的节点，节点已访问说明其所在连通块已处理
            infects = 0;    // 新连通分量 初始一个连通块的初始感染节点数为0
            int blockSize = dfs(root, n, graph, initial_set);   // 以当前初始感染节点为起点开始搜索
            if(infects == 1 && (blockSize > maxSize || (blockSize == maxSize && root < res))){
                // 如果连通块上只有一个感染节点，且这个感染节点所在连通块尺寸更大或者一样索引更小，更新
                maxSize = blockSize;
                res = root;
            }
        }
        if(res < 0){
            // res未更新，说明不存在只有一个感染节点的连通块，因此去掉哪个感染节点效果都一样，取最小索引
            return min_index;
        }
        return res;
    }

    /**
     * 深度优先搜索，访问一个连通块上的所有节点
     * 并统计连通块上初始感染节点数，返回连通块节点个数
     */
    private int dfs(int node, int n, int[][] graph, boolean[] initial_set){
        int cnt = 1;    // 统计连通块上节点个数，初始为1表示node本身
        visited[node] = true;   // 标记node已访问
        if(initial_set[node]){
            infects++;      // 统计连通块初始感染节点数
        }
        for(int i = 0; i < n; i++){
            if (i == node || graph[node][i] == 0) {
                continue;       // 跳过节点本身和不与节点相连的节点}
            }
            if (!visited[i]) {
                cnt += dfs(i, n, graph, initial_set);    // 递归搜索未访问的邻节点，并累加访问的节点个数}
            }
        }
        return cnt;     // 返回统计的节点数
    }
}
